package Datas_Structure.Sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2,5,9,7,3,4,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end){
       //当start小于end才会有元素，才执行
        if (start < end){
           //把数组中的第0个元素作为基数
           int stard = arr[start];
           //排序的下标
           int low = start;
           int high = end;
           //循环找出比标准数大的和比标准数小的
           while (low < high){
               //右边的比标准数大
               while (low<high && stard <= arr[high]){
                   high--;
               }
               //右边比基数小，右边的数替换左边的数
               arr[low] = arr[high];
               //左边的数字比基数小
               while (low<high && stard >= arr[low]){
                   low++;
               }
               //左边比基数大
               arr[high] = arr[low];
           }
           //把基数在赋给arr[low]
           arr[low] = stard;
           //递归排左边
           quickSort(arr,start,low);
           //递归排右边
           quickSort(arr,low+1,high);
       }
    }
}
